package top.fengleifeng.question;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2020年11月23日 5:01 下午
 */
public class Num629K个逆序对数组 {

    class Solution {

        public int kInversePairs(int n, int k) {
            int mod = (int) (1e9 + 7);
            int[][] dp = new int[n + 1][k + 1];

            for (int i = 0; i <= n; i++) {
                dp[i][0] = 1;
            }
            // 枚举i个数字
            for (int i = 2; i <= n; i++) {
                // 枚举逆序对个数
                for (int j = 1; j <= k; j++) {
                    for (int p = Math.max(j - i + 1, 0); p <= j; p++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod;
                    }
                }
            }
            return dp[n][k];
        }
    }

    public static void main(String[] args) {
//        int mod = (int) (1e9 + 7);
//        System.out.println(mod);
        int n = 3;
        int k = 1;
        int i = new Num629K个逆序对数组().new Solution().kInversePairs(n, k);
        System.out.println(i);
    }
}
